
public class fastIntArray {
	int startSize,incSize;
	int numNodes,numAdded;
	int bounds;
	node nodeArray[];
	public static class node {
		int mem[];
		int startLoc;
		int memSz;
		public node(int memSize,int startLocation) {
			memSz = memSize;
			mem = new int[memSize];
			startLoc = startLocation;
		}
		public void add(int location, int val) {
			mem[location - startLoc] = val;
		}
		public int get(int location) {
			return mem[location - startLoc];
		}
	}
	public fastIntArray(int startingSize, int increaseSize) {
		startSize = startingSize;
		incSize = increaseSize;
		bounds+= startingSize;
		nodeArray = new node[20];
		nodeArray[0] = new node(startingSize,0);
		numNodes++;
	}
	public void add(int location, int val) {
		numAdded++;
		while(location >= bounds) {
			addNode();
		}
		if(location < startSize) nodeArray[0].add(location,val);
		else {
			int nodeNum = (int)(((float)location - (float)startSize)/(float)incSize);
			nodeNum++;
			nodeArray[nodeNum].add(location, val);
		}
	}
	public int getNumAdded() { return numAdded; };
	public void addNode() {
		if(numNodes > (nodeArray.length - 1)) resizeNodeArray();
		nodeArray[numNodes] = new node(incSize,bounds);
		numNodes++;
		bounds += incSize;
	}
	public void resizeNodeArray() {
		node newArray[] = new node[nodeArray.length * 2];
		for(int i=0; i < nodeArray.length; i++) {
			newArray[i] = nodeArray[i];
		}
		nodeArray = newArray;
		return;
	}
	public int getNodeNum(int location) {
		if(location < startSize) return 0;
		int nodeNum = (int)(((float)location - (float)startSize)/(float)incSize);
		nodeNum++;
		return nodeNum;
	}
	public int get(int location) {
		return nodeArray[getNodeNum(location)].get(location);
	}
	public void update(int location, int val) {
		if(location < startSize) nodeArray[0].add(location, val);
		else {
		int a = location -  startSize;
		int nodeNum = (int)((float)a/(float)incSize);
		nodeNum++;
		nodeArray[nodeNum].add(location, val);
		}
	}
	public int size() {
		int retval = 0;
		if(numNodes >= 1) retval += startSize;
		retval += incSize * (numNodes - 1);
		return retval;
	}
	public void freeMemory(int size) {
		int numToFree = (size / incSize);
		if(numToFree >= (numNodes - 1)) {
			numToFree = (size - startSize)/incSize;
			if(numToFree >= numNodes) numToFree = numNodes;
		}
		for(int i=0; i < numToFree; i++) {
			nodeArray[numNodes - i - 1] = null;
		}
		numNodes = numNodes - numToFree;
		if(numNodes != 0) bounds = bounds - (numToFree * incSize);
		else bounds = 0;
	}
}
